package com.binarysearch;

import java.util.*;

public class Solution436 {
    public int[] findRightInterval(int[][] intervals) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < intervals.length; i++) {
            map.put(intervals[i][0], i);
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        int[] res = new int[intervals.length];
        for (int[] interval : intervals) {
            int m = 0;
            int n = intervals.length;
            while (m < n) {
                int mid = (m + n) >> 1;
                if (intervals[mid][0] == interval[1]) {
                    m = mid;
                    break;
                } else if (intervals[mid][0] > interval[1]) n = mid;
                else m = mid + 1;
            }
            if (m == intervals.length) res[map.get(interval[0])] = -1;
            else res[map.get(interval[0])] = map.get(intervals[m][0]);
        }
        return res;
    }
}
